/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-islands
   @Language: C++
   @Datetime: 16-02-09 05:13
   */

class Solution {
	void vist(vector<vector<bool> > &grid,int i,int j){
		if (i<0 || i>=grid.size() || j<0 || j>=grid[0].size()
				|| !grid[i][j])
			return;
		grid[i][j]=false;
		vist(grid,i-1,j);
		vist(grid,i+1,j);
		vist(grid,i,j-1);
		vist(grid,i,j+1);
	}

public:
	/**
	 * @param grid a boolean 2D matrix
	 * @return an integer
	 * Tip: Set dot's neighbors (left,right,up,down) as 0
	 */
	int numIslands(vector<vector<bool> > &grid) {
		// Write your code here
		int sum=0;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j){
				if (!grid[i][j]) continue;
				++sum;
				vist(grid,i,j);
			}
		return sum;
	}
};
